import java.awt.Point;
import java.util.ArrayList;
import java.util.Stack;

public class Solution 
{
    private Candidate[][] solution;
    // 'options' will contain the free points (positions) in solution
    // During solving points are moved from 'options' to 'placed'
    private Stack<Point> options, placed;
    
    private static final int BOARDSIZE = 8;
    public static int amountOfSolutions;
    
    
    public Solution(){
        // The 2D array gets an empty ring around it. This helps because when
        // checking the adjacent squares we don't risk a ArrayIndexOutOfBounds
        //  012345
        // 0......
        // 1...-..
        // 2.---..
        // 3..---.
        // 4...-..
        // 5......
        //
        solution = new Candidate[6][6];
        options = new Stack<Point>();
        placed = new Stack<Point>();

        options.push(new Point(4,3));
        options.push(new Point(3,4));
        options.push(new Point(3,3));
        options.push(new Point(3,2)); 
        options.push(new Point(2,3));
        options.push(new Point(2,2));
        options.push(new Point(2,1));
        options.push(new Point(1,3));
    }

    /**
     * Checks whether there are no two same cards lying next to each other.
     * @param Candidate which will be checked if it fits in the current solution.
     * @return Boolean indicating whether this candidate can be put in the
     * next free position
     */
    public boolean fits(Candidate candidate){
        if(candidate.getAvailable() == 0){
            return false;
        }
        
        //Look into the option that is the first on the stack and retrieve it's neighbors
        Point option = options.peek();  
        ArrayList<Candidate> neighbors = getNeighbors(option.x, option.y);
        
        //If candidate has no neighbors at all yet, it's safe to say that the solution is still correct
        if(neighbors.size() == 0)
            return true;
        
        //If a neighbor has the same value as the candidate, the candidate does not fit.
        for(int i = 0; i < neighbors.size(); i++){
            if(neighbors.get(i).value == candidate.value){
                return false;
            }
        }
        
        return true;
    }

    /**
     * Record a candidate onto the solution by popping it from the 'options' stack
     * and placing it on the 'placed' stack and into the solution.
     * @param Candidate that will be recorded onto the solution
     */
    public void record(Candidate candidate)
    {
        Point option = options.pop();
        
        placed.add(new Point(option.x, option.y));
        solution[option.x][option.y] = candidate;
    }
 

    /**
     * Checks whether or not puzzle is completed. Check is based on looking if puzzle is
     * completely filled and all the moves are possible.
     * @return Boolean whether or not puzzle is completed
     */
    public boolean complete()
    {
        if(placed.size() == BOARDSIZE && possible()){
            return true;
        }
        
        return false;
    }

    /**
     * Show results whenever puzzle is solved and keep track of how many solutions have been applied
     */
    public void show()
    {
		amountOfSolutions++;
		System.out.println("Solution #" + amountOfSolutions + ":");
		
		for(int i = 0; i < placed.size(); i++){
    		Point loc = placed.get(i);
    		System.out.println(solution[loc.x][loc.y].value + " at: " + loc.x + ", " + loc.y);
    	}
		System.out.println("\n");
    }

    /**
     * Erase a candidate from the solution by popping it from the 'placed' stack
     * and placing it on the 'options' stack again and removing it from the solution.
     * @return Candidate that has been removed
     */
    public Candidate eraseRecording()
    {
        Point candidateLocation = placed.pop();
        options.add(candidateLocation);
        
        Candidate candidate = solution[candidateLocation.x][candidateLocation.y];
        solution[candidateLocation.x][candidateLocation.y] = null;
        
        return candidate;
    }

    /**
     * Checks whether the following rules are fulfilled:
     * Every ace is positioned next to (horizontal or vertical) to a king (1 to 2).
     * Every king is positioned next to a queen (2 to 3).
     * Every queen is positioned next to a jack (3 to 4).
     * @return Boolean that represents if the candidates are placed according to the rules
     */
    public boolean possible() { 
    	
        //Loop through the placed solutions
        for(int i = 0; i < placed.size(); i++){
            
        	//Get the location of a placed candidate, and retrieve the actual candidate
            Point loc = placed.get(i);
            Candidate candidate = solution[loc.x][loc.y];
            
            //Get the neighbors for this candidate
            ArrayList<Candidate> neighbors = getNeighbors(loc.x, loc.y);
            
            //If the candidate has no neighbors or has neighbor positions left, continue.
            if(neighbors.size() == 0 || neighbors.size() < possibleNeighbors(loc.x, loc.y)){
            	continue;
            }
            
            //Check for each candidate value if it meets the requirement
            boolean hasNeighbor = false;
            if(candidate.value == 1){
            	for(int j = 0; j < neighbors.size(); j++){
            		if(neighbors.get(j).value == 2){
            			hasNeighbor = true;
            		}
            	} if(!hasNeighbor){
            		return false;
            	}
            }
            else if(candidate.value == 2){
            	for(int j = 0; j < neighbors.size(); j++){
            		if(neighbors.get(j).value == 3){
            			hasNeighbor = true;
            		}
            	} if(!hasNeighbor){
            		return false;
            	}
            }
            else if(candidate.value == 3){
            	for(int j = 0; j < neighbors.size(); j++){
            		if(neighbors.get(j).value == 4){
            			hasNeighbor = true;
            		}
            	} if(!hasNeighbor){
            		return false;
            	}
            }
        }
        
        return true;
    }

    /**
     * Return a list of candidates(neighbors) that can be used to check whether or not
     * the candidate fits in the solution.
     * @param x Coordinate of candidate
     * @param y Coordinate of candidate
     * @return ArrayList of candidates that are neighbors
     */
    private ArrayList<Candidate> getNeighbors(int x, int y){
        ArrayList<Candidate> neighbors = new ArrayList<Candidate>();
        
        if(solution[x + 1][y] != null){
            neighbors.add(solution[x + 1][y]);
        }
        if(solution[x][y + 1] != null){
            neighbors.add(solution[x][y + 1]);
        }
        if(solution[x - 1][y] != null){
            neighbors.add(solution[x - 1][y]);
        }
        if(solution[x][y - 1] != null){
            neighbors.add(solution[x][y - 1]);
        }
        
        return neighbors;
    }
    
    /**
     * This method is used to check how many possible neighbor positions are available 
     * for each position. The possible neighbor positions are used to check 
     * if the candidate could still get fitting neighbors if it doesn't have
     * one in the current situation.
     * @param x Coordinate of candidate
     * @param y Coordinate of candidate
     * @return possible amount of neighbors
     */
    private int possibleNeighbors(int x, int y){
    	if(x == 1 && y == 3 || x == 2 && y == 1 || x == 3 && y == 4 || x == 4 && y == 3){
    		return 1;
    	} else if (x == 3 && y == 2 ){
    		return 2;
    	} else if (x == 2 && y == 3  || x == 2 && y == 2){
    		return 3;
    	} else { //if x == 3 && y == 3
    		return 4;
    	}
    }
}